/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._204;

/**
 *
 * 统计所有小于非负整数 n 的质数的数量。
 *
 * 示例:
 *
 * 输入: 10
 * 输出: 4
 * 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._204
 * @ClassName: CountPrimes
 * @Author: linyaonan
 * @Date: 2019/12/2 17:54
 */
public class CountPrimes {

    public int countPrimes(int n) {
        boolean[] notPrim = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            // 一定为素数
            if (!notPrim[i]) {
                count++;
                // 将该值能整除的值全部修改为非素数
                for (int j = 2; j*i < n; j++) {
                    notPrim[j*i] = true;
                }
            }
        }
        return count;
    }

}
